<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>1722：[Usaco2006 Mar] Milk Team Select 产奶比赛</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2006 Mar] Milk Team Select 产奶比赛</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2006 Mar] Milk Team Select 产奶比赛</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2006 Mar] Milk Team Select 产奶比赛                </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：64MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium; ">Farmer John's N (1 &lt;= N &lt;= 500) cows are trying to select the milking team for the world-famous Multistate Milking Match-up (MMM) competition. As you probably know, any team that produces at least X (1 &lt;= X &lt;= 1,000,000) gallons of milk is a winner.  Each cow has the potential of contributing between -10,000 and 10,000 gallons of milk. (Sadly, some cows have a tendency to knock over jugs containing milk produced by other cows.)  The MMM prides itself on promoting family values. FJ's cows have no doubt that they can produce X gallons of milk and win the contest, but to support the contest's spirit, they want to send a team with as many parent-child relationships as possible (while still producing at least X gallons of milk). Not surprisingly, all the cows on FJ's farm are female.  Given the family tree of FJ's cows and the amount of milk that each would contribute, compute the maximum number of parent-child relationships that can exist in a winning team. Note that a set of cows with a grandmother-mother-daughter combination has two parent-child relationships (grandmother-mother, mother-daughter).</span></p>
<p>
<p class="MsoNormal"><span style="font-size: medium; "><br />
</span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">约翰的</span><span lang="EN-US">N(1</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">N</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">500)</span><span style="font-family: 宋体; ">头奶牛打算组队去参加一个世界级的产奶比赛</span><span lang="EN-US">(Multistate&nbsp;Milking</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">Match-up</span><span style="font-family: 宋体; ">，缩写为</span><span lang="EN-US">MMM)</span><span style="font-family: 宋体; ">．她们很清楚其他队的实力，也就是说，她们派出的队只要能产出至少</span><span lang="EN-US">X(I</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">X</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">1000000)</span><span style="font-family: 宋体; ">加仑牛奶，就能赢得这场比赛．</span><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">每头牛都能为集体贡献一定量的牛奶，数值在</span><span lang="EN-US">-10000</span><span style="font-family: 宋体; ">到</span><span lang="EN-US">10000</span><span style="font-family: 宋体; ">之间（有些奶牛总是想弄翻装着其他奶牛产的奶的瓶子）．</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;MMM</span><span style="font-family: 宋体; ">的举办目的之一，是通过竞赛中的合作来增进家庭成员之间的默契．奶牛们认为她们总是能赢得这场比赛，但为了表示对比赛精神的支持，她们希望在选出的队伍里能有尽可能多的牛来自同一个家庭，也就是说，有尽可能多对的牛有直系血缘关系（当然，这支队伍必须能产出至少</span><span lang="EN-US">X</span><span style="font-family: 宋体; ">加仑牛奶）．当然了，所有的奶牛都是女性，所以队伍里所有直系血亲都是母女关系．</span><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">约翰熟知所有奶牛之间的血缘关系．现在他想知道，如果在保证一支队伍能赢得比赛的情况下，队伍中最多能存在多少对血缘关系．注意，如果一支队伍由某头奶牛和她的母亲、她的外祖母组成，那这支队伍里一共有</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">对血缘关系（这头奶牛外祖母与她的母亲，以及她与她的母亲）．</span></span></p>
<p class="MsoNormal"></p>
</p></p><hr/><h3>输入格式</h3><p><p><span style="font-size: medium; ">* Line 1: Two space-separated integers, N and X.  * Lines 2..N+1: Line i+1 contains two space-separated integers         describing cow i. The first integer is the number of gallons         of milk cow i would contribute. The second integer (range         1..N) is the index of the cow's mother. If the cow's mother is         unknown, the second number is 0. The family information has no         cycles: no cow is her own mother, grandmother, etc.&nbsp;</span></p>
<p>
<div><span style="font-size: medium; "><br />
</span></div>
<div>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp; &nbsp;&nbsp;</span><span style="font-family: 宋体; ">第</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">行：两个用空格隔开的整数</span><span lang="EN-US">N</span><span style="font-family: 宋体; ">和</span><span lang="EN-US">X.</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">第</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">到</span><span lang="EN-US">N+1</span><span style="font-family: 宋体; ">行：每行包括两个用空格隔开的整数，第一个数为一只奶牛能贡献出的牛奶的加仑数，第二个数表示她的母亲的编号．如果她的母亲不在整个牛群里，那第二个数为</span><span lang="EN-US">0</span><span style="font-family: 宋体; ">．并且，血缘信息不会出现循环，也就是说一头奶牛不会是自己的母亲或祖母，或者更高代的祖先．</span></span></p>
<p class="MsoNormal"></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp; &nbsp;</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span style="font-family: 宋体; "><br />
</span></span></p>
</div>
</p></p><hr/><h3>输出格式</h3><p><p>* Line 1: The maximum number of parent-child relationships possible on         a winning team. Print -1 if no team can win.</p>
<p></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp; &nbsp;&nbsp;</span><span style="font-family: 宋体; ">输出在一个能获胜的队伍中，最多可能存在的有血缘关系的牛的对数．如果任何一支队伍都不可能获胜，输出</span><span lang="EN-US">-1.</span></span></p>
<p></p></p><hr/><h3>样例输入</h3><pre>5 8
-1 0   //第一个数字代表这头奶的产量,第二个数字代表其父亲点是哪一个.
3 1
5 1
-3 3
2 0

INPUT DETAILS:

There are 5 cows. Cow 1 can produce -1 gallons and has two daughters, cow
2 and 3, who can produce 3 and 5 gallons, respectively. Cow 3 has a
daughter (cow 4) who can produce -3 gallons. Then there's cow 5, who can
produce 2 gallons.

</pre><hr/><h3>样例输出</h3><pre>2

</pre><hr/><h3>提示</h3><p><p>&nbsp;</p>
<div></div>
<div>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp; &nbsp;&nbsp;</span><span style="font-family: 宋体; ">约翰一共有</span><span lang="EN-US">5</span><span style="font-family: 宋体; ">头奶牛．第</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">头奶牛能提供</span><span lang="EN-US">-1</span><span style="font-family: 宋体; ">加仑的牛奶，且她是第</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">、第</span><span lang="EN-US">3</span><span style="font-family: 宋体; ">头奶牛的母亲．第</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">、第</span><span lang="EN-US">3</span><span style="font-family: 宋体; ">头奶牛的产奶量务别为</span></span><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="3" unitname="加仑" w:st="on"></st1:chmetcnv><span style="font-size: medium; "><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="3" unitname="加仑" w:st="on"><span lang="EN-US">3</span><span style="font-family: 宋体; ">加仑</span></st1:chmetcnv><span style="font-family: 宋体; ">和</span></span><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="5" unitname="加仑" w:st="on"></st1:chmetcnv><span style="font-size: medium; "><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="5" unitname="加仑" w:st="on"><span lang="EN-US">5</span><span style="font-family: 宋体; ">加仑</span></st1:chmetcnv><span style="font-family: 宋体; ">．第</span><span lang="EN-US">4</span><span style="font-family: 宋体; ">头奶牛是第</span><span lang="EN-US">3</span><span style="font-family: 宋体; ">头奶牛的女儿，她能提供</span><span lang="EN-US">-3</span><span style="font-family: 宋体; ">加仑牛奶．还有与其他牛都没有关系的第</span><span lang="EN-US">5</span><span style="font-family: 宋体; ">头奶牛，她的产奶量是</span></span><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="2" unitname="加仑" w:st="on"></st1:chmetcnv><span style="font-size: medium; "><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="2" unitname="加仑" w:st="on"><span lang="EN-US">2</span><span style="font-family: 宋体; ">加仑</span></st1:chmetcnv><span style="font-family: 宋体; ">．</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">最好的一支队伍包括第</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">，</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">，</span><span lang="EN-US">3</span><span style="font-family: 宋体; ">，</span><span lang="EN-US">5</span><span style="font-family: 宋体; ">头奶牛．她们一共能产出（</span><span lang="EN-US">-1</span><span style="font-family: 宋体; ">）</span><span lang="EN-US">+3+5+2=9</span><span style="font-family: 宋体; ">&ge;</span><span lang="EN-US">8</span><span style="font-family: 宋体; ">加仑牛奶，</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span style="font-family: 宋体; ">并且这支队伍里有</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">对牛有血缘关系（</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">&mdash;</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">和</span><span lang="EN-US">1-3</span><span style="font-family: 宋体; ">）．如果只选第</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">，</span><span lang="EN-US">3</span><span style="font-family: 宋体; ">，</span><span lang="EN-US">5</span><span style="font-family: 宋体; ">头奶牛，虽然总产奶量会更高（</span></span><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="10" unitname="加仑" w:st="on"></st1:chmetcnv><span style="font-size: medium; "><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="10" unitname="加仑" w:st="on"><span lang="EN-US">10</span><span style="font-family: 宋体; ">加仑</span></st1:chmetcnv><span style="font-family: 宋体; ">），但这支队伍里包含的血缘关系的对数比上一种组合少（队伍里没有血缘关系对）．</span></span></p>
</div>
<div></div></p><hr/><h3>题目来源</h3><p>Gold</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=1722" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1722" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>